<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html>
  <head>
    <title>Java bytecode constraints</title>
    <link rel=stylesheet href="java-constraints.css">
  </head>

  <body>
    <h1>
      Bytecode constraints
    </h1>

    <p>
      From the point of view of a piece of code written in the Java
      programming language or targeted in the same way to <code>.class</code>
      files, the Dalvik VM aims to behave in a way
      that is fully consistent with the language's definition.
      That is, the code running in Dalvik will behave the same as it
      would have running in any other virtual machine. This includes
      verification failures.
      The Dx/Dalvik system will check roughly the same
      constraints that any other VM would, except as noted in the file
      <a href="verifier.html">verifier.html</a>. The following table briefly
      lists all Dx/Dalvik verification constraints together their analogs
      from the book <i>The Java<super>TM</super> Language Specification</i>,
      second edition. In the numbering scheme, the first three
      elements refer to the specification chapter, the fourth one to the
      bullet inside that chapter. The failure mode specifies whether the
      constraint will fail during the Dx conversion or during verification in
      the VM itself.
    </p>

    <h2>
      Static constraints
    </h2>

    <p>
    Static constraints are constraints on individual elements of the bytecode.
    They usually can be checked without employing control or data-flow analysis
    techniques.
    </p>

    <table>
      <tr>
        <th>
          Identifier
        </th>

        <th>
          Description
        </th>

        <th>
          Spec equivalent
        </th>

        <th>
          Failure mode
        </th>
      </tr>

      <tr>
        <td>
          A1
        </td>

        <td>
          The <code>code</code> array must not be empty.
        </td>

        <td>
          4.8.1.1
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          A2
        </td>

        <td>
          The <code>code</code> array must not be larger than 65535 bytes.
        </td>

        <td>
          4.8.1.2
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          A3
        </td>

        <td>
          The first opcode in <code>code</code> array must have index
          <code>0</code>.
        </td>

        <td>
          4.8.1.3
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          A4
        </td>

        <td>
          The <code>code</code> array must only contain valid opcodes.
        </td>

        <td>
          4.8.1.4
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          A5
        </td>

        <td>
          The index of instruction <code>n+1</code> must equal the index of
          instruction <code>n</code> plus the length of instruction
          <code>n</code>, taking into account a possible <code>wide</code>
          instruction. Opcodes modified by a <code>wide</code> instruction must
          not be directly reachable.
        </td>

        <td>
          4.8.1.5
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          A6
        </td>

        <td>
          The last instruction in <code>code</code> array must end at index
          <code>code_length-1</code>.
        </td>

        <td>
          4.8.1.6
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          A7
        </td>

        <td>
          All jump and branch targets must be opcodes within the same method.
          Opcodes modified by a <code>wide</code> instruction must not be
          directly reachable via a jump or branch instruction.
        </td>

        <td>
          4.8.1.7
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          A8
        </td>

        <td>
          All targets of a <code>tableswitch</code> instruction must be opcodes
          within the same method. Upper and lower bounds must be consistent.
          Opcodes modified by a <code>wide</code> instruction must not be
          directly reachable via a <code>tableswitch</code> instruction.
        </td>

        <td>
          4.8.1.8
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          A9
        </td>

        <td>
          All targets of a <code>lookupswitch</code> instruction must be opcodes
          within the same method. Its table must be consistent and sorted
          low-to-high. Opcodes modified by a <code>wide</code> instruction must
          not be directly reachable via a <code>lookupswitch</code> instruction.
        </td>

        <td>
          4.8.1.9
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          A10
        </td>

        <td>
          The operands of <code>ldc</code> and <code>ldc_w</code> instructions
          must be valid indices into the constant pool. The respective entries
          must be of type <code>CONSTANT_Integer</code>,
          <code>CONSTANT_Float</code>, or <code>CONSTANT_String</code>.
        </td>

        <td>
          4.8.1.10
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          A11
        </td>

        <td>
          The operands of <code>ldc2_w</code> instructions must be valid indices
          into the constant pool. The respective entries must be of type
          <code>CONSTANT_Long</code> or <code>CONSTANT_Double</code>. The
          subsequent constant pool entry must be valid and remain unused.
        </td>

        <td>
          4.8.1.11
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          A12
        </td>

        <td>
          The Operands of <code>get&lt;kind&gt;</code> and
          <code>put&lt;kind&gt;</code> instructions must be valid indices into
          constant pool. The respective entries must be of type
          <code>CONSTANT_Fieldref</code>.
        </td>

        <td>
          4.8.1.12
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          A13
        </td>

        <td>
          The first two operands of <code>invokevirtual</code>,
          <code>invokespecial</code>, and <code>invokestatic</code> must form a
          valid 16-bit index into the constant pool. The respective entries must
          be of type <code>CONSTANT_Methodref</code>.
        </td>

        <td>
          4.8.1.13
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          A14
        </td>

        <td>
          Methods whose names start with '<' must only be invoked implicitly by
          the VM, not by class file code. The only exception is the instance
          initializer, which may be invoked by <code>invokespecial</code>.
        </td>

        <td>
          4.8.1.14
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          A15
        </td>

        <td>
          The first two operands of <code>invokeinterface</code> must form a
          valid 16-bit index into the constant pool. The entry must be of type
          <code>CONSTANT_Interface_Methodref</code>. The third operand must
          specify number of local variables and the fourth operand must always
          be zero.
        </td>

        <td>
          4.8.1.15
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          A16
        </td>

        <td>
          The operands of <code>instanceof</code>, <code>checkcast</code>,
          <code>new</code>, and <code>anewarray</code> instructions must
          be a valid index into the constant pool. The first two operands of
          <code>multianewarray</code> instruction must form a valid 16-bit index
          into the constant pool. All respective entries must be of type
          <code>CONSTANT_Class</code>.
        </td>

        <td>
          4.8.1.16
        </td>

        <td>
          DX
        </td>
      </tr>

     <tr>
        <td>
          A17
        </td>

        <td>
          The dimensions of an array created by <code>anewarray</code>
          instructions must be less than <code>256</code>.
        </td>

        <td>
          4.8.1.17
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          A18
        </td>

        <td>
          The <code>new</code> instruction must not reference array classes,
          interfaces, or abstract classes.
        </td>

        <td>
          4.8.1.18
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          A19
        </td>

        <td>
          The type referenced by a <code>multinewarray</code> instruction must
          have at least as many dimensions as specified in the instruction. The
          dimensions operand must not be <code>0</code>
        </td>

        <td>
          4.8.1.19
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          A20
        </td>

        <td>
          The type referenced by a <code>newarray</code> instruction must be a
          valid, non-reference type.
        </td>

        <td>
          4.8.1.20
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          A21
        </td>

        <td>
          The index operand of instructions explicitly referencing single-width
          local variables must be non-negative and smaller than
          <code>max_locals</code>.
        </td>

        <td>
          4.8.1.21
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          A22
        </td>

        <td>
          The index operand of instructions implicitly referencing single-width
          local variables must be non-negative and smaller than
          <code>max_locals</code>.
        </td>

        <td>
          4.8.1.22
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          A23
        </td>

        <td>
          The index operand of instructions explicitly referencing double-width
          local variables must be non-negative and smaller than
          <code>max_locals-1</code>.
        </td>

        <td>
          4.8.1.23
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          A24
        </td>

        <td>
          The index operand of instructions implicitly referencing double-width
          local variables must be non-negative and smaller than
          <code>max_locals-1</code>.
        </td>

        <td>
          4.8.1.24
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          A25
        </td>

        <td>
          The index operand of <code>wide</code> instructions explicitly
          referencing single-width local variables must be non-negative and
          smaller than <code>max_locals</code>.
        </td>

        <td>
          4.8.1.25
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          A26
        </td>

        <td>
          The index operand of <code>wide</code> instructions explicitly
          referencing double-width local variables must be non-negative and
          smaller than <code>max_locals-1</code>.
        </td>

        <td>
          4.8.1.25
        </td>

        <td>
          DX
        </td>
      </tr>
    </table>

    <h2>
      Structural constraints
    </h2>

    <p>
    Structural constraints are constraints on relationships between several
    elements of the bytecode. They usually can't be checked without employing
    control or data-flow analysis techniques.
    </p>

    <table>
      <tr>
        <th>
          Identifier
        </th>

        <th>
          Description
        </th>

        <th>
          Spec equivalent
        </th>

        <th>
          Failure mode
        </th>
      </tr>

      <tr>
        <td>
          B1
        </td>

        <td>
          The number and types of arguments (operands and local variables) must
          always match the instruction.
        </td>

        <td>
          4.8.2.1
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          B2
        </td>

        <td>
          The operand stack must have the same depth for all executions paths
          leading to an instruction.
        </td>

        <td>
          4.8.2.2
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          B3
        </td>

        <td>
          Local variable pairs must never be broken up.
        </td>

        <td>
          4.8.2.3
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          B4
        </td>

        <td>
          A local variable (or pair) has to be assigned first before it can be
          read.
        </td>

        <td>
          4.8.2.4
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          B5
        </td>

        <td>
          The operand stack must never grow beyond <code>max_stack</code>.
        </td>

        <td>
          4.8.2.5
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          B6
        </td>

        <td>
          The operand stack must never underflow.
        </td>

        <td>
          4.8.2.6
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          B7
        </td>

        <td>
          An <code>invokespecial</code> instruction must only invoke an instance
          initializer or a method in the current class or one of its
          superclasses.
        </td>

        <td>
          4.8.2.7
        </td>

        <td>
          VM
        </td>
      </tr>

      <tr>
        <td>
          B8
        </td>

        <td>
          An instance initializer must only be invoked on an uninitialized
          instance residing on the operand stack.
        </td>

        <td>
          4.8.2.8
        </td>

        <td>
          VM
        </td>
      </tr>

      <tr>
        <td>
          B9
        </td>

        <td>
          Instance methods may only be invoked on and instance fields may only
          be accessed on already initialized instances.
        </td>

        <td>
          4.8.2.9
        </td>

        <td>
          VM
        </td>
      </tr>

      <tr>
        <td>
          B10
        </td>

        <td>
           The must be no backwards branches with uninitialized instances on the
           operand stack or in local variables. There must be no code protected
           by an exception handler that contains local variables with
           uninitialized instances.
        </td>

        <td>
          4.8.2.10
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          B11
        </td>

        <td>
           An instance initializer must call another instance initializer (same
           class or superclass) before any instance members can be accessed.
           Exceptions are non-inherited instance fields, which can be assigned
           before calling another initializer, and the <code>Object</code> class
           in general.
        </td>

        <td>
          4.8.2.11
        </td>

        <td>
          VM
        </td>
      </tr>

      <tr>
        <td>
          B12
        </td>

        <td>
           All actual method arguments must be assignment-compatible with formal
           arguments.
        </td>

        <td>
          4.8.2.12
        </td>

        <td>
          VM
        </td>
      </tr>

      <tr>
        <td>
          B13
        </td>

        <td>
           For each instance method invocation, the actual instance must be
           assignment-compatible with the class or interface specified in the
           instruction.
        </td>

        <td>
          4.8.2.13
        </td>

        <td>
          VM
        </td>
      </tr>

      <tr>
        <td>
          B14
        </td>

        <td>
           A returns instruction must match its method's return type.
        </td>

        <td>
          4.8.2.14
        </td>

        <td>
          VM
        </td>
      </tr>

      <tr>
        <td>
          B15
        </td>

        <td>
           When accessing protected members of a superclass, the actual type of
           the instance being accessed must be either the current class or one
           of its subclasses.
        </td>

        <td>
          4.8.2.15
        </td>

        <td>
          VM
        </td>
      </tr>

     <tr>
        <td>
          B16
        </td>

        <td>
           The type of a value stored into a static field must be
           assignment-compatible with or convertible to the field's type.
        </td>

        <td>
          4.8.2.16
        </td>

        <td>
          VM
        </td>
      </tr>

      <tr>
        <td>
          B17
        </td>

        <td>
           The type of a value stored into a field must be assignment-compatible
           with or convertible to the field's type.
        </td>

        <td>
          4.8.2.17
        </td>

        <td>
          VM
        </td>
      </tr>

      <tr>
        <td>
          B18
        </td>

        <td>
           The type of every value stored into an array must be
           assignment-compatible with the array's component type.
        </td>

        <td>
          4.8.2.18
        </td>

        <td>
          VM
        </td>
      </tr>

      <tr>
        <td>
          B19
        </td>

        <td>
           The operand of an <code>athrow</code> instruction must be
           assignment-compatible with <code>java.lang.Throwable</code>.
        </td>

        <td>
          4.8.2.19
        </td>

        <td>
          VM
        </td>
      </tr>

      <tr>
        <td>
          B20
        </td>

        <td>
           The last reachable instruction of a method must either be a backwards
           jump or branch, a return, or an <code>athrow</code> instruction. It
           must not be possible to leave the <code>code</code> array at the
           bottom.
        </td>

        <td>
          4.8.2.20
        </td>

        <td>
          VM
        </td>
      </tr>

      <tr>
        <td>
          B21
        </td>

        <td>
           Local variable values must not be used as return addresses.
        </td>

        <td>
          4.8.2.21
        </td>

        <td>
          VM
        </td>
      </tr>

      <tr>
        <td>
          B22
        </td>

        <td>
          There must be a single, uniquely determined return instruction per
          subroutine call.
        </td>

        <td>
          4.8.2.22
        </td>

        <td>
          VM
        </td>
      </tr>

      <tr>
        <td>
          B23
        </td>

        <td>
          Subroutine calls must not be directly or indirectly self-recursive.
        </td>

        <td>
          4.8.2.23
        </td>

        <td>
          DX
        </td>
      </tr>

      <tr>
        <td>
          B24
        </td>

        <td>
           <code>ReturnAddress</code> instances must not be reused. If a
           subroutine returns to a <code>ReturnAddress</code> further up the
           stack than where its original call instruction is located, then all
           <code>ReturnAddress</code> instances further down the stack must
           never be used.
        </td>

        <td>
          4.8.2.24
        </td>

        <td>
          DX
        </td>
      </tr>

    </table>
  </body>
</html>
